package com.company.duilieAndzhan;


import com.sun.javaws.jnl.MatcherReturnCode;
import com.sun.org.apache.bcel.internal.generic.RETURN;
import com.sun.org.apache.regexp.internal.RE;
import com.sun.org.apache.regexp.internal.REUtil;
import com.sun.org.apache.xalan.internal.xsltc.compiler.util.StringStack;
import org.junit.Test;

import javax.swing.*;
import java.util.*;
import java.util.function.BinaryOperator;

/**
 * @description:
 * @author: Code-zyc
 * @date: Created in 2021/11/17 12:24
 * @version: 1.0
 * @modified By:
 */
public class Testdui {

    @Test
    public void testmethd() {

        List<List<Integer>> rooms=new ArrayList<>();

        List one= new ArrayList<Integer>();
        one.add(1);
        one.add(3);
        rooms.add(one);

        List two= new ArrayList<Integer>();
        two.add(3);
        two.add(0);
        two.add(1);
        rooms.add(two);

        List three= new ArrayList<Integer>();
        three.add(2);
        rooms.add(three);

        List four= new ArrayList<Integer>();
        four.add(0);
        rooms.add(four);

        boolean b = canVisitAllRooms(rooms);
        System.out.println(b);

    }

    /**
     * 钥匙和房间
     * 有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
     *
     * 在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
     *
     * 最初，除 0 号房间外的其余所有房间都被锁住。
     *
     * 你可以自由地在房间之间来回走动。
     *
     * 如果能进入每个房间返回 true，否则返回 false。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/gle1r/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

    boolean [] vised;
    int count;

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int size = rooms.size();
        vised=new boolean[size];
        dfscanVisitAllRooms(rooms,0);
        return count==size;
    }
    public void dfscanVisitAllRooms(List<List<Integer>> rooms,int dex){
        vised[dex]=true;
        count++;
        for (Integer item:rooms.get(dex)){
                if (!vised[item]){
                    dfscanVisitAllRooms(rooms,item);
                }
        }
    }

    public boolean canVisitAllRooms2(List<List<Integer>> rooms) {
        List<Integer> yaoshi=new ArrayList<>(); //用来存放找到的钥匙
        Set<Integer> used=new HashSet<>(); //用来存放用过的钥匙
        List<Integer> lists = rooms.get(0);//先拿到  第0个房间的钥匙
        //然后 把0钥匙 存进used
        used.add(0);
        //把拿到的钥匙 存到set里面
        for (Integer item :lists){
            yaoshi.add(item);
        }

        int count=0;  //  我的 yaoshi这个集合 一直在增加 所以进行循环的时候 拿个count记录一下
        while (true){

            int size = yaoshi.size();
            //如果 size 不变就证明结束了 没有能拿到的钥匙 （不一定指钥匙全拿完）
            //只有used 的数量 等于了roms的数量 才能返回true
            if(size==count || used.size()==(rooms.size())){
                if (used.size()==(rooms.size())){
                    return true;
                }else {
                    return false;
                }
            }

            //然后利用已经有的钥匙房去访问 其他房间
            for (int i=0+count;i<size;i++){
                //拿钥匙进房间  前看看 这钥匙是不是用过  用过就不用去了避免死循环
                if (!used.contains(yaoshi.get(i))){
                    //开始进房间  并讲房间里面的钥匙 收集起来
                    List<Integer> integers = rooms.get(yaoshi.get(i));
                    for (Integer integer :integers){
                        yaoshi.add(integer);
                    }
                    //把用过的钥匙 存放起来
                    used.add(yaoshi.get(i));

                }

            }

            //把size传给count  下一次的起始的查询地址 就是 count开始了
            count=size;
        }



    }

    /**
     * 01 矩阵
     * 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
     * <p>
     * 两个相邻元素间的距离为 1 。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/g7pyt/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public int[][] updateMatrix(int[][] matrix) {
        // 首先将所有的 0 都入队，并且将 1 的位置设置成 -1，表示该位置是 未被访问过的 1
        Queue<int[]> queue = new LinkedList<>();
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[] {i, j});
                } else {
                    matrix[i][j] = -1;
                }
            }
        }

        int[] dx = new int[] {-1, 1, 0, 0};
        int[] dy = new int[] {0, 0, -1, 1};
        while (!queue.isEmpty()) {
            int[] point = queue.poll();//一次取出0
            int x = point[0], y = point[1]; //这是0的坐标
            for (int i = 0; i < 4; i++) {  //这一步是进行上下左右遍历
                int newX = x + dx[i];
                int newY = y + dy[i];
                // 如果四邻域的点是 -1，表示这个点是未被访问过的 1
                // 所以这个点到 0 的距离就可以更新成 matrix[x][y] + 1。
                if (newX >= 0 && newX < m && newY >= 0 && newY < n
                        && matrix[newX][newY] == -1) {
                    matrix[newX][newY] = matrix[x][y] + 1;
                    queue.offer(new int[] {newX, newY});
                }
            }
        }

        return matrix;
    //    作者：sweetiee
//    链接：https://leetcode-cn.com/problems/01-matrix/solution/2chong-bfs-xiang-jie-dp-bi-xu-miao-dong-by-sweetie/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    }



    public int[][] updateMatrix2(int[][] mat) {
        int ilength = mat.length; //记录长度
        int jlength = mat[0].length;
        int[][] result = new int[ilength][jlength]; //存放结果
        for (int i = 0; i < ilength; i++) {
            for (int j = 0; j < jlength; j++) {
                if (mat[i][j] != 0) {
                    //不等于0 开始进行广度遍历
                    int count = 0; //记录广度的层数
                    Queue<Integer> queue = new LinkedList();//队列 存放查询的数据
                    queue.add(mat[i][j]);//初始给个值
                    boolean flag=false;  //标志找到最短路径没有
                    while (true) {
                        //把队列里面这一层的全部拿出来对比
                        while (!queue.isEmpty()){
                            //如果等于0 那就存放结果
                            if (queue.poll()==0){
                                result[i][j]=count;
                                flag=true;
                                break;
                            }
                        }
                        //找到了马上退出
                        if (flag){
                            break;
                        }
                        //层数相加  因为对应的那一层已经匹配玩了
                        count++;

                        //把上下左右的元素  加进队列中 层数加一 注意边界的问题

                        int templei=i;
                        int templej=j;
                        for (int i1 = 1; i1 <=count; i1++) {

                            if (templei - 1 >= 0 ) {
                                queue.add(mat[templei - 1][templej]);
                            }
                            if (templei + 1 < mat[0].length ) {
                                queue.add(mat[templei + 1][templej]);
                            }
                            if (templej - 1 >= 0) {
                                queue.add(mat[templei][templej - 1]);
                            }
                            if (templej + 1 < mat[0].length ) {
                                queue.add(mat[templei][templej + 1]);
                            }


                        }

                    }

                }
                //如果等于不需要操作 初始就是0
            }
        }
        return result;
    }

    /**
     * 图像渲染
     * 有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
     * <p>
     * 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
     * <p>
     * 为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/g02cj/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        //判断一下如果一样那就不需要上色了
        if (newColor == image[sr][sc]) {
            return image;
        }
        floodFillDigui(image, sr, sc, newColor, image[sr][sc]);
        return image;
    }

    void floodFillDigui(int[][] image, int sr, int sc, int newColor, int value) {
        if (image[sr][sc] == value) {
            //表示符合要替换的值  就替换成newclor
            image[sr][sc] = newColor;
            //然后看实深度搜索（上下左右乱走）
            //往上
            if (sr > 0) {
                floodFillDigui(image, sr - 1, sc, newColor, value);
            }
            //往下
            if (sr < image.length - 1) {
                floodFillDigui(image, sr + 1, sc, newColor, value);
            }
            //往左
            if (sc > 0) {
                floodFillDigui(image, sr, sc - 1, newColor, value);
            }
            //往右
            if (sc < image[0].length - 1) {
                floodFillDigui(image, sr, sc + 1, newColor, value);
            }
        }

        //如果不等于就 或者到达边界就返回去了 不需要往哪走了
        return;

    }

    /**
     * 符串解码
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     * <p>
     * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
     * <p>
     * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
     * <p>
     * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/gdwjv/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

//    int count = 0; //记录遍历的

    public String decodeString(String s) {
        Stack<Integer> numberstack = new Stack<>();//存放数字的
        Stack<String> stringStack = new Stack();//存放字符串
        char[] chars = s.toCharArray();
        while (count < chars.length) {
            if ('0' <= chars[count] && chars[count] <= '9') {
                //判断是不是 数字
                //这个函数主要是 找这个数字是多少
                Integer number = getnumber(chars);
                numberstack.push(number);
            } else if (Character.isLetter(chars[count]) || chars[count] == '[') {
                //如果是  字母和【 就近栈
                stringStack.push(chars[count] + "");
                count++;
            } else {
                //如果都不是 就是’】‘ 开始进行操作
                //思路 从stringStack 提字母
                // 直到遇到【  然后从numberstack 提数字进行循环
                StringBuilder builder = new StringBuilder();
                while (!"[".equals(stringStack.peek())) {
                    builder.insert(0, stringStack.pop());
                }
                //把【 移除
                stringStack.pop();
                //临时字符串  主要是用来循环
                StringBuilder templestring = new StringBuilder();
                //然后提出数字进行循环
                Integer number = numberstack.pop();
                for (Integer i = 0; i < number; i++) {
                    templestring.append(builder);
                }
                //循环完  把字符串放回去
                stringStack.push(templestring.toString());
                //记得游标往前走
                count++;
            }


        }

        //最后只需要把stirngstack 的拿出来
        StringBuilder templestring = new StringBuilder();
        while (!stringStack.empty()) {
            templestring.insert(0, stringStack.pop());
        }
        return templestring.toString();
    }


    //这个函数主要是 找数字是多少 比如100【acd】 这个函数就负责返回100
    private Integer getnumber(char[] chars) {
        Integer result = 0;
        int temple = count; //临时坐标
        int sum = 0; //记录有几位数
        while ('0' <= chars[temple] && chars[temple] <= '9') {

            sum++;
            temple++;
        }

        int j = 1;
        for (int i = sum; i > 0; i--) {
            result = result + (chars[count + i - 1] - '0') * j;
            j = j * 10;
        }

        //移动游标到 数字后面
        count = count + sum;
        return result;
    }

    /**
     * 二叉树的中序遍历
     * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
     */

//      Definition for a binary tree node.
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//
//        TreeNode() {
//        }
//
//        TreeNode(int val) {
//            this.val = val;
//        }
//
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }
//    List<Integer> result=new ArrayList<>();
//    public List<Integer> inorderTraversal(TreeNode root) {
//        inorderTraversalstatic(root);
//        return result;
//    }
//
//    private void inorderTraversalstatic(TreeNode root) {
//        if (root==null){
//            return;
//        }else {
//            inorderTraversalstatic(root.left);
//            result.add(root.val);
//            inorderTraversalstatic(root.right);
//        }
//    }


    /**
     * 目标和
     * 给你一个整数数组 nums 和一个整数 target 。
     * <p>
     * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
     * <p>
     * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
     * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/ga4o2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public int findTargetSumWays(int[] nums, int target) {
        int result = 0;
        result = findTargetSumWaysStack(nums, 0, target, 0);
        return result;
    }

    private int findTargetSumWaysStack(int[] nums, int index, int target, int count) {

        if (nums.length <= index + 1) {
            if (Math.abs(target) == nums[index]) {
                //针对0的特殊性
                if (target == 0) {
                    count = count + 2;
                    return count;
                }
                return ++count;
            } else {
                return count;
            }
        }
        count = findTargetSumWaysStack(nums, index + 1, target + nums[index], count);
        count = findTargetSumWaysStack(nums, index + 1, target - nums[index], count);
        return count;

    }


    /**
     * 克隆图
     * 给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
     * <p>
     * 图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/gmcr6/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

// Definition for a Node.
    class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    public Node cloneGraph(Node node) {
        return clone(node, new HashMap<>());
    }

    public Node clone(Node node, HashMap<Integer, Node> visited) {
        //边界条件判断
        if (node == null)
            return null;
        //如果当前节点已经创建了，直接返回
        if (visited.containsKey(node.val))
            return visited.get(node.val);
        //否则创建当前节点
        Node newNode = new Node(node.val, new ArrayList<>());
        //把创建的节点存放到map中
        visited.put(newNode.val, newNode);
        //创建当前节点的邻居节点
        for (Node neighbor : node.neighbors)
            newNode.neighbors.add(clone(neighbor, visited));
        return newNode;
    }


    /**
     * 逆波兰表达式求值
     * 根据 逆波兰表示法，求表达式的值。
     * <p>
     * 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
     */

    public int evalRPN(String[] tokens) {
        int length = tokens.length;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            if ("+".equals(tokens[i])) {
                Integer one = stack.pop();
                Integer two = stack.pop();
                stack.push(one + two);
            } else if ("-".equals(tokens[i])) {
                Integer one = stack.pop();
                Integer two = stack.pop();
                stack.push(two - one);
            } else if ("*".equals(tokens[i])) {
                Integer one = stack.pop();
                Integer two = stack.pop();
                stack.push(one * two);
            } else if ("/".equals(tokens[i])) {
                Integer one = stack.pop();
                Integer two = stack.pop();
                stack.push(two / one);
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }

    /**
     * 完全平方数
     * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
     * <p>
     * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
     * <p>
     * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/kfgtt/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public int numSquares(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];


    }

    /**
     * 每日温度
     * 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。
     * 如果气温在这之后都不会升高，请在该位置用 0 来代替
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        if (length == 1 || length == 0) {
            return new int[]{0};
        }
//        Map<Integer,Integer> map=new HashMap<>();
        int[] result = new int[length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
                continue;
            }
            if (temperatures[i] <= temperatures[stack.peek()]) {
                stack.push(i);
            } else {
                while ((!stack.isEmpty()) && temperatures[i] > temperatures[stack.peek()]) {
                    Integer pop = stack.pop();
                    result[pop] = i - pop;
                }
                stack.push(i);
            }
        }

        return result;
    }

    /**
     * 有效的括号
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * <p>
     * 有效字符串需满足：
     * <p>
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/g9d0h/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public boolean isValid(String s) {

        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '{' || chars[i] == '[' || chars[i] == '(') {
                stack.push(chars[i]);
            } else {

                try {
                    Character pop = stack.pop();
                    if (chars[i] == ')' && pop != '(') {
                        return false;
                    }
                    if (chars[i] == ']' && pop != '[') {
                        return false;
                    }
                    if (chars[i] == '}' && pop != '{') {
                        return false;
                    }
                } catch (Exception e) {
                    return false;
                }
            }
        }
        return stack.isEmpty();


    }

    boolean isValidzhan(char[] chars, int count) {
        if (count == -1) {
            return true;
        }
        if (chars[count] == '}' || chars[count] == ')' || chars[count] == ']') {
            return isValidzhan(chars, --count);

        } else {
            if (count == chars.length - 1) {
                return false;
            } else {
                switch (chars[count]) {
                    case '(':
                        if (chars[count + 1] == ')') {
                            return isValidzhan(chars, --count);
                        } else {
                            return false;
                        }
                    case '[':
                        if (chars[count + 1] == ']') {
                            return isValidzhan(chars, --count);
                        } else {
                            return false;
                        }
                    case '{':
                        if (chars[count + 1] == '}') {
                            return isValidzhan(chars, --count);
                        } else {
                            return false;
                        }
                    default:
                        return false;
                }
            }
        }
    }

    /**
     * 打开转盘锁
     * 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
     * <p>
     * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
     * <p>
     * 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
     * <p>
     * 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/kj48j/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     **/

    public int openLock(String[] deadends, String target) {
        String start = "0000";
        if (start.equals(target)) {
            return 0;
        }
        if (baohan(start, deadends) || baohan(target, deadends)) {
            return -1;
        }

        int count = openLockDiGui(deadends, target, start, 0);
        if (count == 0) {
            return -1;
        }
        return count;
    }

    int openLockDiGui(String[] deadends, String target, String start, int count) {

        if (baohan(start, deadends)) {
            return count;
        }
        char[] charsstart = start.toCharArray();
        char[] charstarget = target.toCharArray();

        for (int i = 0; i < 4; i++) {
            if (charsstart[i] != charstarget[i]) {
                //第i位
                int state = charsstart[i];
                //上下移动
                int up = state + 1 % 10;
                int de = (state - 1 % 10) == -1 ? 9 : (state - 1 % 10);

            }
        }


        return 0;


    }

    boolean baohan(String start, String[] deadends) {
        for (int i = 0; i < deadends.length; i++) {
            if (start.equals(deadends[i])) {
                return true;
            }
        }
        return false;
    }


    /**
     * 岛屿数量
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * <p>
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * <p>
     * 此外，你可以假设该网格的四条边均被水包围。
     * <p>
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/queue-stack/kbcqv/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    bianli(grid, i, j);
                }
            }
        }
        return count;
    }

    private void bianli(char[][] grid, int i, int j) {

        int lengthi = grid.length;
        int lengthj = grid[0].length;

        grid[i][j] = 0;
        //上下左右
        if (i > 0 && grid[i - 1][j] == '1') {
            bianli(grid, i - 1, j);
        }
        if (i < lengthi - 1 && grid[i + 1][j] == '1') {
            bianli(grid, i + 1, j);
        }
        if (j > 0 && grid[i][j - 1] == '1') {
            bianli(grid, i, j - 1);
        }
        if (j < lengthj - 1 && grid[i][j + 1] == '1') {
            bianli(grid, i, j + 1);
        }
    }


}
